package com.esri.core.geometry;

/* loaded from: classes.dex */
class Treap {
    private TreapComparator e;
    private AttributeStreamOfInt32 f;
    private int c = 124234251;
    private int a = nullNode();
    private int b = nullNode();
    private int d = 0;

    public static int nullNode() {
        return -1;
    }

    private int a(int i) {
        return this.f.get(i + 3);
    }

    private void b(int i) {
        int left = getLeft(i);
        int right = getRight(i);
        int a = a(i);
        while (true) {
            if (left == nullNode() && right == nullNode()) {
                return;
            }
            int a2 = left != nullNode() ? a(left) : NumberUtils.intMax();
            int a3 = right != nullNode() ? a(right) : NumberUtils.intMax();
            if (a <= Math.min(a2, a3)) {
                return;
            }
            if (a2 <= a3) {
                e(left);
            } else {
                d(i);
            }
            left = getLeft(i);
            right = getRight(i);
        }
    }

    private void c(int i) {
        int a = a(i);
        int parent = getParent(i);
        while (parent != nullNode() && a(parent) > a) {
            if (getLeft(parent) == i) {
                e(i);
            } else {
                d(parent);
            }
            parent = getParent(i);
        }
    }

    private void d(int i) {
        int right = getRight(i);
        a(right, getParent(i));
        a(i, right);
        int left = getLeft(right);
        c(i, left);
        if (left != nullNode()) {
            a(left, i);
        }
        b(right, i);
        int parent = getParent(right);
        if (parent != nullNode()) {
            if (getLeft(parent) == i) {
                b(parent, right);
            } else {
                c(parent, right);
            }
        }
    }

    private void e(int i) {
        int parent = getParent(i);
        a(i, getParent(parent));
        a(parent, i);
        int right = getRight(i);
        b(parent, right);
        if (right != nullNode()) {
            a(right, parent);
        }
        c(i, parent);
        int parent2 = getParent(i);
        if (parent2 != nullNode()) {
            if (getLeft(parent2) == parent) {
                b(parent2, i);
            } else {
                c(parent2, i);
            }
        }
    }

    private void a(int i, int i2) {
        this.f.set(i + 2, i2);
    }

    private void b(int i, int i2) {
        this.f.set(i + 0, i2);
    }

    private void c(int i, int i2) {
        this.f.set(i + 1, i2);
    }

    private void d(int i, int i2) {
        this.f.set(i + 3, i2);
    }

    private int f(int i) {
        this.d++;
        if (this.b != nullNode()) {
            int i2 = this.b;
            this.b = this.f.get(i2);
            b(i2, nullNode());
            d(i2, b());
            setElement(i2, i);
            return i2;
        }
        int size = this.f.size();
        this.f.add(nullNode());
        this.f.add(nullNode());
        this.f.add(nullNode());
        this.f.add(b());
        this.f.add(i);
        return size;
    }

    private void a(int i, boolean z) {
        if (i == nullNode()) {
            return;
        }
        a(i, nullNode());
        if (z) {
            a(getRight(i), true);
            a(getLeft(i), true);
        }
        c(i, nullNode());
        b(i, this.b);
        this.b = i;
        this.d--;
    }

    private int b() {
        int nextRand = NumberUtils.nextRand(this.c);
        this.c = nextRand;
        return nextRand & (NumberUtils.intMax() >> 1);
    }

    private int g(int i) {
        if (i == nullNode()) {
            return 0;
        }
        return Math.max(g(getLeft(i)), g(getRight(i))) + 1;
    }

    /* loaded from: classes.dex */
    static abstract class TreapComparator {
        abstract int a(int i, int i2);

        TreapComparator() {
        }
    }

    public Treap() {
        AttributeStreamOfInt32 attributeStreamOfInt32 = new AttributeStreamOfInt32(0);
        this.f = attributeStreamOfInt32;
        attributeStreamOfInt32.reserve(256);
    }

    public void setComparator(TreapComparator treapComparator) {
        this.e = treapComparator;
    }

    TreapComparator a() {
        return this.e;
    }

    public int addElement(int i) {
        int right;
        int f = f(i);
        if (this.a == nullNode()) {
            this.a = f;
            return f;
        }
        int i2 = this.a;
        while (true) {
            if (this.e.a(i, getElement(i2)) < 0) {
                right = getLeft(i2);
                if (right == nullNode()) {
                    b(i2, f);
                    a(f, i2);
                    break;
                }
                i2 = right;
            } else {
                right = getRight(i2);
                if (right == nullNode()) {
                    c(i2, f);
                    a(f, i2);
                    break;
                }
                i2 = right;
            }
        }
        c(f);
        if (getParent(f) == nullNode()) {
            this.a = f;
        }
        return f;
    }

    public void deleteElement(int i) {
        d(i, NumberUtils.intMax());
        int nullNode = nullNode();
        int nullNode2 = nullNode();
        int i2 = this.a;
        boolean z = i2 == i;
        if (z) {
            nullNode = getLeft(i2);
            nullNode2 = getRight(this.a);
            if (nullNode == nullNode() && nullNode2 == nullNode()) {
                a(this.a, false);
                this.a = nullNode();
                return;
            }
        }
        b(i);
        int parent = getParent(i);
        if (parent != nullNode()) {
            if (getLeft(parent) == i) {
                b(parent, nullNode());
            } else {
                c(parent, nullNode());
            }
        }
        a(i, false);
        if (z) {
            if (nullNode == nullNode() || getParent(nullNode) != nullNode()) {
                nullNode = nullNode2;
            }
            this.a = nullNode;
        }
    }

    public int search(int i) {
        int i2 = this.a;
        while (i2 != nullNode()) {
            int a = this.e.a(i, getElement(i2));
            if (a == 0) {
                return i2;
            }
            if (a < 0) {
                i2 = getLeft(i2);
            } else {
                i2 = getRight(i2);
            }
        }
        return nullNode();
    }

    public int getElement(int i) {
        return this.f.get(i + 4);
    }

    public int getLeft(int i) {
        return this.f.get(i + 0);
    }

    public int getRight(int i) {
        return this.f.get(i + 1);
    }

    public int getParent(int i) {
        return this.f.get(i + 2);
    }

    public int getNext(int i) {
        int right = getRight(i);
        if (right != nullNode()) {
            int nullNode = nullNode();
            while (right != nullNode()) {
                int i2 = right;
                right = getLeft(right);
                nullNode = i2;
            }
            return nullNode;
        }
        int parent = getParent(i);
        while (true) {
            int i3 = parent;
            int i4 = i;
            i = i3;
            if (i != nullNode()) {
                if (getLeft(i) == i4) {
                    return i;
                }
                parent = getParent(i);
            } else {
                return nullNode();
            }
        }
    }

    public int getPrev(int i) {
        int left = getLeft(i);
        if (left != nullNode()) {
            int nullNode = nullNode();
            while (left != nullNode()) {
                int i2 = left;
                left = getRight(left);
                nullNode = i2;
            }
            return nullNode;
        }
        int parent = getParent(i);
        while (true) {
            int i3 = parent;
            int i4 = i;
            i = i3;
            if (i != nullNode()) {
                if (getRight(i) == i4) {
                    return i;
                }
                parent = getParent(i);
            } else {
                return nullNode();
            }
        }
    }

    public int getFirst() {
        int i = this.a;
        while (i != nullNode()) {
            int left = getLeft(i);
            if (left == nullNode()) {
                return i;
            }
            i = left;
        }
        return nullNode();
    }

    public int getLast() {
        int i = this.a;
        while (i != nullNode()) {
            int right = getRight(i);
            if (right == nullNode()) {
                return i;
            }
            i = right;
        }
        return nullNode();
    }

    public void setElement(int i, int i2) {
        this.f.set(i + 4, i2);
    }

    public int getRoot() {
        return this.a;
    }

    public void clear() {
        a(this.a, true);
    }

    public int size() {
        return this.d;
    }

    public int getMaxDepth() {
        return g(this.a);
    }
}
